using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;

namespace QuadTreeExample
{
    class QTNode
    {
        string id = "";
        int depth;

        public int Depth
        {
            get { return depth; }
            set { depth = value; }
        }

        QTNode[] children = new QTNode[4];

        List<NodeData> data;

        double xMin;
        double xMax;
        double yMin;
        double yMax;


        bool hasChildren;



        #region Properties
        public string Id
        {
            get { return id; }
        }
        internal QTNode[] Children
        {
            get { return children; }
            set { children = value; }
        }
        public List<NodeData> Data
        {
            get { return data; }
            set { data = value; }
        }


        public double XMin
        {
            get { return xMin; }
            set { xMin = value; }
        }
        public double XMax
        {
            get { return xMax; }
            set { xMax = value; }
        }
        public double YMin
        {
            get { return yMin; }
            set { yMin = value; }
        }
        public double YMax
        {
            get { return yMax; }
            set { yMax = value; }
        }
        public bool HasChildren
        {
            get { return hasChildren; }
        }
        #endregion

        public QTNode()
        {

        }
        public QTNode(double xMinIn, double xMaxIn, double yMinIn, double yMaxIn, string idIn)
        {
            depth = 0;
            id = idIn;
            xMin = xMinIn;
            xMax = xMaxIn;
            yMin = yMinIn;
            yMax = yMaxIn;
        }


        internal void Partition()
        {
            //0 Upper Left
            //1 Upper Right
            //2 Lower Left
            //3 Lower Right

            children[0] = new QTNode();
            children[0].id = this.id + "A";
            children[0].depth = this.depth + 1;
            children[0].XMin = (this.xMin);
            children[0].XMax = ((this.xMin + this.XMax) / 2.0);
            children[0].YMin = (this.yMin);
            children[0].YMax = ((this.yMin + this.yMax) / 2.0);

            children[1] = new QTNode();
            children[1].id = this.id + "B";
            children[1].depth = this.depth + 1;
            children[1].XMin = ((this.xMin + this.XMax) / 2.0);
            children[1].XMax = (this.XMax);
            children[1].YMin = (this.yMin);
            children[1].YMax = ((this.yMin + this.yMax) / 2.0);



            children[2] = new QTNode();
            children[2].id = this.id + "C";
            children[2].depth = this.depth + 1;
            children[2].XMin = (this.xMin);
            children[2].XMax = ((this.xMin + this.XMax) / 2.0);
            children[2].YMin = ((this.yMin + this.yMax) / 2.0);
            children[2].YMax = (this.yMax);

            children[3] = new QTNode();
            children[3].id = this.id + "D";
            children[3].depth = this.depth + 1;
            children[3].XMin = ((this.xMin + this.xMax) / 2.0);
            children[3].XMax = (this.XMax);
            children[3].YMin = ((this.yMin + this.yMax) / 2.0);
            children[3].YMax = (this.yMax);

            hasChildren = true;
        }

        public override string ToString()
        {
            return id;
        }
    }

    class NodeData
    {
        double x;

        public double X
        {
            get { return x; }
            set { x = value; }
        }
        double y;

        public double Y
        {
            get { return y; }
            set { y = value; }
        }
        object data;

        public object Data
        {
            get { return data; }
            set { data = value; }
        }
    }
}
